package py.una.pol.paralelos;

public class Prim {

	/**
	 * @param args
	 */
	public static void execute(Graph graph) {

		Vertex VT[] = new Vertex[graph.getNumVertexs()];
		VT[graph.getR()] = graph.getV(graph.getR());

		int d[] = new int[graph.getNumVertexs()];
		int a[] = new int[graph.getNumVertexs()]; // To keep edges

		for (int v = 0; v < graph.getNumVertexs(); v++) {
			if (VT[v] == null) {
				if (graph.getW(graph.getR(), v) > 0) {
					d[v] = graph.getW(graph.getR(), v);
					a[v] = graph.getR();
				} else {
					d[v] = -1;
					a[v] = graph.getR();
				}

			}
		}

		
		/////////////////////////////////////////////////////////
		
		int u = 0;
		for (int v = 0; v < graph.getNumVertexs(); v++) {
			if (VT[v] == null) {
				if (d[v] > 0) {
					u = v;
				}
			}
		}

		for (int v = 0; v < graph.getNumVertexs(); v++) {
			int min = d[u];
			if (VT[v] == null) {
				if (d[v] < min & d[v] > 0) {
					min = d[v];
					u = v;
				}
				if (d[v] == min) {
					System.out.println("arbol");
					subrutine(v ,graph, VT, d,a,"");
					
				}
			}
		}

	}

	public static void subrutine(int root, Graph graph, Vertex VT[], int d[], int a[], String tree) {
		// calculate d
//		System.out.println("Choose " + graph.getV(root).getLabel() + "from " + graph.getV(a[root]).getLabel());
		String myTree = tree + "\t" + graph.getV(a[root]).getLabel() + " - " + graph.getV(root).getLabel() ;
		Vertex[] myVT = VT.clone();
		myVT[root] = graph.getV(root);
		int mya[] = a.clone();
		
		int[] myd = d.clone();
		
		int total = 0;
		for(int v = 0; v < graph.getNumVertexs(); v++){
			if(myVT[v] != null){
				total++;
			}
		}
		if(total == graph.getNumVertexs()){
			System.out.println(myTree);
			
			return;
		}
		
		for (int v = 0; v < graph.getNumVertexs(); v++) {
			if (myVT[v] == null) {
				if (myd[v] > graph.getW(root, v) & graph.getW(root, v) > 0) {
					myd[v] = graph.getW(root, v);
					mya[v] = root;
				}
				if (myd[v] == -1 & graph.getW(root, v) > 0) {
					myd[v] = graph.getW(root, v);
					mya[v] = root;
				}
			}
		}
		
		int u = 0;
		
		
		for (int v = 0; v < graph.getNumVertexs(); v++) {
			if (myVT[v] == null) {
				if (myd[v] > 0) {
					u = v;
				}
			}
		}

		for (int v = 0; v < graph.getNumVertexs(); v++) {
			int min = myd[u];
			if (myVT[v] == null) {
				if (myd[v] < min & myd[v] > 0) {
					min = myd[v];
					u = v;
				}
				if (myd[v] == min) {
					subrutine(v ,graph, myVT, myd,mya,myTree);
				}
			}
		}

	}

}
